package name.huzhenbo.java.algorithm.search;

class TargetSearch {
    /**
     * Quick sort
     * Tail recursive, that under best condition, the time complexity is O(n)
     *
     * @param input
     * @param target
     * @return
     */
    public int go(int[] input, int target) {
        return _go(input, 0, input.length - 1, target);
    }

    private int _go(int[] input, int start, int end, int target) {
        if (start > end) {
            return 0;
        }
        if (start == end) {
            return input[start];
        }
        int i = start + 1;
        int j = end;
        while (true) {
            while (i < end && input[i] < input[start]) {
                i++;
            }
            while (j > start && input[j] > input[start]) {
                j--;
            }
            if (j <= i) {
                break;
            }
            swap(input, i, j);
        }
        swap(input, start, j);
        if (j > target) {
            return _go(input, start, j - 1, target);
        } else if (j < target) {
            return _go(input, j + 1, end, target);
        } else {
            return input[j];
        }
    }

    private void swap(int[] input, int i, int j) {
        int temp = input[i];
        input[i] = input[j];
        input[j] = temp;
    }
}
